亿展宏图 第四篇|当图算法遇到大数据

作者|陈圣茜&韩志超

编辑|林颖

供稿|eBay支付风控团队

本文共4891字，预计阅读时间10分钟

更多干货请关注“eBay技术荟”公众号

导读

“亿展宏图”是eBay 支付风控团队推出的系列文章，分享了eBay风控团队工作在图算法方面的一些理解和研究。在上期的亿展宏图 第三篇|如何高性能训练图神经网络里，我们介绍了训练图神经网络的三种图采样范式和DeGNN算法，以此来更高性能地训练图神经网络。本期亿展宏图，我们将介绍在图算法中解决海量数据的方法。

引 言

在大数据场景中，海量的数据往往意味着超大的图，这会影响到我们对问题的处理速度，各类算法的应用也会受到限制。如下面这张梯形漏斗图（为了数据安全性考虑，我们图中展示的是假数据，不过大致和我们真实数据的数量级比较近似），可见每一次进行缩小处理之后都会发生很大量级的变化。

那每一次的缩小处理是采用什么方法，适用的场景又是什么样的呢？下面就带大家从构图开始，一步一步来看如何处理图太大的问题，每一步处理过程中又有哪些取舍问题需要考虑。

一

全量交易图

要建立全量交易图，主要有两个步骤：1是构图；2是去掉超级节点。

1、构图

构建图就是在构建关系网络，所以这张网的构建一定要从解决问题的实际场景出发。在风控场景中，账号之间的重叠信息和真实的交易行为是构图的重要信息来源。基于这样的认知，我们往往会选择注册账号的邮件、电话、支付信息等作为账号之间的边。

然而，有时可选择的关联信息会有很多，那哪些信息对挖掘风险是更有效的呢？
这时，我们引入同质偏好的概念。同质偏好是指个体更倾向于与他们相似的个体建立连结，即“物以类聚”。我们标注已知的风险点为“label1”，未知风险点为“0”，且n0为label的节点数量，n1为非label的节点数量。然后，我们定义三类二元组，分别为(1, 1)、(1, -0)和(0, -0)。它们分别表示(label1, -label1)、(label1, -label0)和(label0, -label0)形式的两点一边。再计算每一类二元组的节点数量总和，分别为m₁₁、m₁₀和m₀₀，得到：

如果点和点之间的边是随机连接的，与他们本身的风险点(label)并无关系，那么m₁₁和m₁₀的期望值（如下公式计算得到）应该是相等的。

其中p = 2M/(N(N – 1))，代表两个节点相连的概率。如果p=1, 那么图中所有的点都互相连接。现在我们定义dyadicity(D) 和 heterophilicity(H)：

如果一个网络中D>1, 表示这个网络是dyadic的，这表示相比随机连接，风险节点彼此连接得更紧密。如果H<1，表示这个网络是heterophobic的，这意味着相比随机连接，风险节点和非风险节点之间连接得更少。如果一个网络同时满足dyadic和heterophobic，那就说明这个网络表现为同质性。利用这两个数值，可以帮助我们判断，一个关系（边）是否能够很好地展现出网络的同质性，进而有利于风险社团的挖掘。在样本数据中，我们使用了如上图所示的边关系，其中支付账号或卡片(Payment token)和注册地址(Registration address)展示了非常高的dyadicity值，其余类型的dyadictiy也均大于1，可见这些标签都是有意义的关联关系。在交易数据中，确定好点和边后，我们就可以搭建相关场景的图（如下图所示）。

(点击可查看大图)

2、去掉超级节点

因为一些公共信息是共享的，比如咖啡厅/网吧IP、企业的对公账户、枢纽机场等，会使得这些节点拥有超过平均值几倍甚至几十倍的边，如下图中间部分的超大节点，我们称之为超级节点。

网络图^[1]

在风控场景中，这些重度连接的节点趋向于快速累积更多链路，这使得具有少量边的节点被忽视掉；而超级节点也会使得图迅速变大且难以分割。所以，在构图之后，移除超级节点是第一步有效缩减图的方式。比较直接的方法是：根据所有节点度(degree)的分布，设定一个阈值，当一个节点的度高于这个阈值的时候，就去掉这个节点。

二

风险交易图

在全量交易图中，包含着海量的数据，其中包含一些无关紧要的信息。这就需要对图进行“瘦身”，从而得到我们关注的信息——风险交易图。我们一般采取K跳算法对图进行瘦身。

K跳算法(K-hop)在业务层面非常便于理解且操作，可以称得上是最简便的缩小图网络的方式，因此被广泛使用。K跳算法指的是从某个顶点出发，寻找到所有与其最短路径为K跳（或K步）的顶点的集合。它可以根据K值大小来调整得到缩小图后的大小，通常进行K跳算法之后，一张超级大图会有一个量级的减小，但每个k值对应的结果是固定的。在风控场景中，将已知的风险节点标注为标签，然后以这些风险节点出发，顺着构建好的边往外延伸，保留k层与之关联的所有节点，最后用保留的节点再构建连通图。子图的扩张顺序正如下图所示。

（点击可查看大图）

三

风险社群

在进一步缩小图至风险社群过程中，我们常用连通图、标签传播算法、幂迭代聚类这三种方法。

1、连通图

     (Connected Components)

连通图^[2] 

如果从顶点A到顶点B有路径相连，则称A和B是连通的。如果一个图中的任意两点都是连通，那么图被称作连通图。以连通图的定义，K跳后的图可以被切割成一个个子图这些子图就可作为天然的社区，从而进行分割。图的连通性是图的基本性质。以连通图作为切割小图的方式，是非常直观和自然的。由连通图得到的分割结果是唯一的，但往往还是会存在超大图。

2、标签传播算法

     (label propagation algorithm,LPA)

LPA的社区划分方式可以改善上述不够灵活的问题。LPA是基于标签传播的局部社区划分算法。如下图所示，首先给每个点一个标签，在一轮迭代中，再将每一个节点选择与之相连的节点中占比最高的标签作为自己的标签，若占比相等就随机选择。如此迭代到最终稳定或者规定的轮数之后，只保留有风险节点存在的社区，这样就可进一步缩小图了。

在实际应用中， LPA的迭代十分迅速有效率。但因为传播的随机性，划分结果并不稳定（甚至会出现标签震荡、两个点不能出现在同一个社区的情况）。如上图所示，四个节点为一个小社区在两次经过标签传播后，得到了完全不同的结果。LPA的另一个问题是在传播结束后，会看到有很多孤立的点不在任何社区内，在我们的例子中这样的节点占比超过了20%。

3、幂迭代聚类

     (power iteration clustering,PIC)

如果我们想尽量不出现孤立点，让每个节点都有自己归属的社群，那么可以使用PIC来做社区划分。PIC适合对大型稀疏矩阵，即节点之间的关联关系矩阵，进行运算。简单来说，PIC 由两部分组成：

1）对稀疏的邻接矩阵做维度变换。

就如同下图所示的从三维地球仪表面到二维地图平面的映射， 这一步维度的变化可以让数据对聚类算法的表征能力有所提高。

维度变换^[3]

2）针对变换后的数据做聚类。

维度变换后，需对数据进行如下迭代步骤：

① 输入按行归一化的关联关系矩阵W，和期望聚类数k；

② 随机选取一个非零初始向量；

③ 计算

并使得

④ 增加t，重复迭代步骤③，直到

为止；

⑤ 使用k-means对向量中的点进行聚类；

⑥ 输出社团C₁， C₂，...， C𝚔。

PIC的具体原理有更复杂的论证，具体可以参考这篇论文：power iteration clustering^[4]。

PIC的特点是可以用提前停止(early stopping)来快速有效地找到特征向量(eigen vector)，得到一个低维空间的映射，这个映射后的数据恰好是适合聚类的特征输入。这样，PIC会更均匀地切分社区，且不会有孤立点存在，很好地解决了LPA丢失太多孤立点的问题。如下图所示，我们以一个中心点加两圈同心圆的图为例，PIC在经过多轮迭代后，能完美地切分出三个社区。

Power Iteration Clustering^[5] 

（点击查看大图）

连通图、LPA、PIC这三种算法都可以缩小图，得到风险社区。但它们都有各自的优缺点，如下表所示：

那么在我们的实际例子中，基于这三种算法得到的社群到底是什么样的呢？我们通过下面这些统计值来看一下：

总而言之，连通图的社群关系比较便于理解，有连边就属于一个社群，不存在不确定性也不需要主观优化目标设定。但它的缺点是：容易出现超大集群，通常容易被类似公共IP或者转运仓库等信息噪声较大的节点关联到一起。LPA的标签传播逻辑也并不复杂，且快速有效，但缺点是表现不稳定，容易出现大量孤立节点。如果下游应用关心的是颗粒度较细的关联关系，且不关心原本联结就松散的社群关系，那么LPA是个好的选择。而联通关系紧密的社群会较高可能地被暴露出来，大部分社群数量都不超过10个，当然预期的规模大小可以通过迭代次数来控制。如果下游应用还会有后续分解步骤或者聚类算法的话，PIC是个合适的选择。它可以先高效地分离出大社群，这里社群个数的选取不涉及业务含义，一般会结合下游算法的处理能力和并行规模而决定。

四

高危社群

所谓“乱花渐欲迷人眼”，在包含有大量交易的交易图网络中，简单的缩小和切割后得到的缩小图中，还是无法让人一眼聚集到图的某一个可疑网络，我们就需要对网络进行做可视化。那在可视化的时候，图太大的问题要怎么解决呢？区域性社区检测(local community detection,LCD)就能很好地帮我们解决这一问题做到这一点。

对于LCD，首先我们来了解一下谱聚类(spectral clustering)，因为后面要介绍的两个算法都是在此基础上做了一些变动。传统的谱聚类是基于特征向量来进行社区划分的算法，具体步骤如下：1）构造图对应的相似矩阵S∈n×n，并确定社区个数k；

2）根据S构建邻接矩阵W和度矩阵D，并算出拉普拉斯矩阵L；

3）计算L的前k个特征向量u1, …, uk，把u1, ..., uk组成矩阵U，U∈n×k；

4）U中的一行作为一个样本，对n个样本做K-means聚类，由此输出k个群落。

由于传统的谱聚类无法设定社区的最小规模，也无法避免最终输出时社区之间可能存在的大小失衡，我们采用以下这些优化过的算法：

1、ACL 

(Spectral Clustering with ACL Approximate PageRank Vectors)^[6]

网页排名(pagerank)算法中，我们知道最终转移概率矩阵•PRV=PRV，所以PRV(pagerank vector)是特征向量，其特征值为1。
而ACL算法提出了一种近似算法得到特征向量，从而能大大地提高运行速度。ACL可以在指定点附近找到一个相对小的社区，且计算时间与这个小社区的规模成正比（对比整个网络图，可以节省计算时间）。与传统谱聚类不同的是，我们需要设定一个起始点和一些其他超参数来计算PR(PageRank)向量，并以一些条件来搜索社区。在我们的样本数据中，选取一个较大的子图，如下图所示，其中绿色表示订单，黄色表示与其有连接关系的实体（地址、电话号码、邮件等等）。在图中随机选择一个起始点，得到以通过acl算法筛选出的点为中心的局部社区，即在一个相对较大的联通图上得到更贴近目标节点的邻居节点。这些更有关系的邻居节点，用放大的节点表示。此外，在ACL的基础上使用l1-regularized PageRank(PR)这一优化目标，并用FISTA来得到最优解^[7]。用上述的改良算法，应用在相同的样本和起始点，得到的社区与ACL完全一致。

(点击可查看大图)

2、MQI

(Max Flow Quotient Cut Improvement)^[8]

在ACL探测完一个社区后，有时候这个社区还是相对较大或者连着旁枝末节。这时，我们可以使用MQI在已经寻找出的社区里寻找一个更优社区。

MQI的做法是在给定的规模不大的参考节点里找到一个拥有最优的连通率(conductance)的社区作为返回值。我们就在上图ACL切分出来的社区基础上，用MQI优化，呈现出来的社区如下图所示：

(点击可查看大图)

在得到这个社区之后我们就可以放大缩小坐标系，来查看聚焦的小社区，也可以做进一步的检验或分析。

总结

现在是大数据的时代，这就导致构建完的图网络往往是一张超级大图。这既提供了更多信息，同时也带来了很大的挑战。本期亿展宏图，我们针对图太大的问题，提到了去除超级节点，并使用K跳算法缩小网络，然后把仍然过大的图通过LPA或者PIC进行分割,最后可以用LCD聚焦到高风险社群。在这篇文章中使用的方法各有优缺点，它们既可以被单独使用，也可以结合在一起。在实际应用中，我们可以结合场景和期望达到的效果，灵活地使用这些技巧来解决图过大的问题。
下一期“亿展宏图”，我们将介绍异构图的深度学习模型和xFraud异构图算法模型，敬请期待！

参考资料:

[1]https://www.acspri.org.au/summer-program -2020/network-analysis-social-business-and-political-research

[2]https://en.wikipedia.org/wiki/Strongly_connected _component

[3]https://www.earthdatascience.org/courses /earth-analytics/spatial-data-r/intro-to-coordinate -reference-systems/

[4]http://www.cs.cmu.edu/~wcohen/postscript /nips-2009-pic.pdf

[5]Power Iteration Clustering www.cs.cmu.edu /~frank/papers/icml2010-pic-final.pdf

[6]http://www.math.ucsd.edu/~fan/wp/localpartition.pdf

[7]https://arxiv.org/pdf/1602.01886.pdf

[8]https://link.springer.com/chapter/10.1007/ 978-3-540-25960-2_25

往期推荐

亿展宏图 第一篇|两张图入门图算法

亿展宏图 第二篇|图算法在eBay支付风控领域的应用

亿展宏图 第三篇|如何高性能训练图神经网络

点击阅读原文，一键投递

        eBay大量优质职位虚席以待

        我们的身边，还缺一个你